package com.leetcode;

//Leetcode 208
public class Trie {
    /**
     * 时间复杂度 ：L * O(1)； L是字符串的长度,O(1)是每个字符查询的时间复杂度，通过数组下标来访问，所以时间复杂度是0(1)；
     * 控件复杂度 ： 26*L（26的 L 次幂，L是字符串长度）,即每次插入一个新的字符，需要创建一个长度为26的数组
     */
    private Trie[] children;
    private boolean isEnd;

    public Trie() {
        children = new Trie[26];
        isEnd = false;
    }

    public void insert(String word) {
        Trie node = this;
        //头结点是一个空节点
        //每一个节点下面挂一个Trie对象数组，数组长度是26，对应26个英文字母
        for (int i = 0; i < word.length(); i++) {
            char ch = word.charAt(i);
            //将字母转换成下标，后续可以快速的访问
            int index = ch - 'a';
            if (node.children[index] == null) {
                node.children[index] = new Trie();
            }
            node = node.children[index];
        }
        node.isEnd = true;
    }

    public boolean search(String word) {
        Trie node = searchPrefix(word);
        return node != null && node.isEnd;
    }

    public boolean startsWith(String prefix) {
        return searchPrefix(prefix) != null;
    }

    private Trie searchPrefix(String prefix) {
        Trie node = this;
        for (int i = 0; i < prefix.length(); i++) {
            char ch = prefix.charAt(i);
            int index = ch - 'a';
            if (node.children[index] == null) {
                return null;
            }
            node = node.children[index];
        }
        return node;
    }


    public static void main(String[] args) {
//["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
//[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
        Trie trie = new Trie();
        trie.insert("apple");
        System.out.println(trie.search("apple"));

        System.out.println(trie.search("app"));
        System.out.println(trie.startsWith("app"));
        trie.insert("app");
        System.out.println(trie.search("app"));
    }
}
